// 解法1：双指针，基本思想：对两个数组先排序，然后使用两个指针left1和left2分别指向两个数组的第一个元素
// 如果nums[left1] 等于nums2[left2],则加入答案数组，并将两个指针右移
// 如果nums[left1] 小于 nums2[left2],则将left1右移
// 如果nums[left1] 大于 nums2[left2],则将left2右移
// 最后输出答案数组

function intersection(arr1, arr2) {
    arr1.sort((x, y) => x - y)
    arr2.sort((x, y) => x - y)
    let left1 = 0
    let left2 = 0
    let res = []
    while (left1 < arr1.length && left2 < arr2.length) {
        if (arr1[left1] === arr2[left2]) {
            if (!res.includes(arr1[left1])) {
                res.push(arr1[left1])
            }
            left1 += 1
            left2 += 1
        } else if (arr1[left1] < arr2[left2]) {
            left1 += 1
        } else if (arr1[left1] > arr2[left2]) {
            left2 += 1
        }
    }
    return res
}

// 解法2：哈希表
// 1. 先遍历第一个数组，利用哈希表来存放第一个数组的元素，对应字典值设为1
// 2. 然后遍历第二个数组，如果哈希表中存在该元素，则将该元素加入到答案数组中，并且将该键值清空
function intersection(nums1, nums2) {
    let numDict = new Map()
    let nums = []
    for (let i = 0; i < nums1.length; i++) {
        if (!numDict.has(nums1[i])) {
            numDict.set(nums1[i], 1)
        }
    }
    for (let i = 0; i < nums2.length; i++) {
        if ((numDict.has(nums2[i]) && numDict.get(nums2[i]) !== 0)) {
            numDict.set(nums2[i], numDict.get(nums2[i]) - 1)
            nums.push(nums2[i])
        }
    }
    return nums
}

let arr1 = [4, 9, 5]
let arr2 = [9, 4, 9, 8, 4]
console.log(intersection(arr1, arr2));